//https://leetcode.cn/problems/binary-tree-preorder-traversal/

class Solution {
public:
    vector<int> preorderTraversal(TreeNode* root) {
        TreeNode* cur = root;
        stack<TreeNode*> st;
        vector<int> ret;

        //先访问左节点，再访问左路节点，最后访问左节点的右子树
        while (cur || !st.empty())
        {
            //访问左节点及左路节点
            while (cur)
            {
                ret.push_back(cur->val);
                st.push(cur);
                cur = cur->left;
            }

            //带左节点的右子树入栈
            TreeNode* top = st.top();
            st.pop();

            //转化成右子树的子问题
            cur = top->right;
        }
        return ret;
    }
};